import java.util.Arrays;
import java.util.Objects;

/**
 * 功能：
 * 作者：lc
 * 日期：2024/9/21 18:45
 */
public class Algorithm_002_1_FindNumber {
    // 为了验证
    public static void main(String[] args) {
        Integer N=100;
        Integer V=1000;
        Integer testTime=50000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            Integer n= (int) (Math.random()*N);
            Integer[] arr=randomArray(N,V);
            Arrays.sort(arr);
            Integer num= (int) (Math.random()*N);
            if (right(arr,num)!=exist(arr,num)){
                System.out.println("出错了！");
            }
        }
        System.out.println("测试结束！");
    }

    //验证
    public static Integer[] randomArray(Integer n,Integer v){
        Integer[] arr=new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i]=(int) (Math.random()*v)+1;
        }
        return arr;
    }

    // 对数器
    // 保证arr有序，使用该方法
    public static boolean right(Integer[] sortedArr, Integer num) {
        for (int cur :
                sortedArr) {
            if (cur == num) {
                return true;
            }
        }
        return false;
    }

    // 保证arr有序，使用该方法
    public static boolean exist(Integer arr[], Integer num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        Integer l = 0, r = arr.length - 1, m = 0;
        while (l <= r) {
            m = (l + r) / 2;
            if (Objects.equals(arr[m], num)) {
                return true;
            } else if (arr[m] > num) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return false;
    }
}
